Problem :

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.

Example 1 :

**Input: nums = [1,3,5,6], target = 5
Output: 2**

Example 2 :

**Input: nums = [1,3,5,6], target = 2
Output: 1**

Example 3 :

**Input: nums = [1,3,5,6], target = 7
Output: 4**

核心思維 :

1. 利用 left + (right - left) / 2 搜尋陣列的中間值 nums[mid]
2. 進行二分搜尋法持續至找出並回傳目標值 target

• 若中間值 nums[mid] 與 目標值 target 相等，則回傳目標值 target
• 若中間值 nums[mid] 小於 目標值 target ，將左指標設定為中間值 nums[mid] + 1
• 若中間值 nums[mid] 大於 目標值 target ，將右指標設定為中間值 nums[mid] - 1

3. 二分搜尋法的搜尋結束後未找到目標值 target ，將目標值設為左指標並回傳其索引值

程式碼 :

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //設定左指標索引值為0，右指標索引值為陣列長-1
        int left = 0, right = nums.size() - 1;  
        while ( left <= right) {
            //設定中間值
            int mid = left + (right - left) / 2;
            //當中間值與目標值相同，回傳目標值
            if( target == nums[mid]){
                return mid;
            }
            //當中間值小於目標值，調整左指標        
            else if(nums[mid] < target){
                left = mid + 1;
            }
            //當中間值大於目標物，調整右指標
            else{
                right = mid - 1;
            }
        }
        //若未找到目標值，將目標值設為左指標並回傳其索引值
        return left;
    }
};

結論 :

這裡利用二分搜尋法來處理排序陣列的問題，首先找出中間值並利用目標值的大小來決定接下來尋找目標值得方向，重複利用相同的步驟縮小搜尋範圍，持續至找到且回傳目標值，若發現目標值不在範圍內，便將目標值設為左指標並回傳其索引值，這一題與第二天的題目十分的相似，差別在要將未找到的目標值插入陣列當中，可以說是延伸題型。